package woa.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangpeng
 * @version 1.0
 * @date 2024/11/18 17:31
 */
public class LRUCache {

    private int capacity;
    private int size;
    private Map<Integer, Node> map = new HashMap<>();
    Node head, tail;


    class Node {
        int key, val;
        Node prev, next;

        public Node() {
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取缓存
     * 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1
     *
     * @param key
     * @return
     */
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }

        moveToHead(node);
        return node.val;
    }
    /**
     * 设置缓存
     * 如果密钥不存在，则写入其数据值
     * 当缓存容量达到上限时，删除最近最少使用的数据值
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            moveToHead(node);
            node.val = value;
            return;
        }

        if (size >= capacity) {
            Node rn = removeTail();
            map.remove(rn.key);
            size--;
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);
        size++;
    }

    private Node removeTail() {
        Node rn = tail.prev;
        removeNode(rn);
        return rn;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

}
